package 动态规划9月;
// https://leetcode-cn.com/problems/fibonacci-number/
public class DP509斐波那契数09182117 {
    class Solution {
        // public int fib(int n) {
        //     if(n==0) return 0;
        //     if(n<=2) return 1;
        //     return fib(n-1)+fib(n-2);
        // }

        // public int fib(int n){
        //     if(n==0)return 0;
        //     int a=1;int  b=1;
        //     for(int i=2;i<n;i++){
        //         b=a+b;
        //         a=b-a;
        //     }
        //     return b;
        // }

        public int fib(int n){
            if(n==0) return 0;
            if(n==1) return 1;
            int a=0,b=1,c=0;
            for(int i=1;i<n;i++){
                c=a+b;
                a=b;
                b=c;
            }
            return c;
        }

    }
}
